"""
构建一个链表：实现 1.头部增加数据 2.尾部增加数据 3.打印链表 4.删除 5.查找
"""


class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class ListNode:
    def __init__(self):
        self.head = None

    # 1.头部增加数据
    def insert_at_head(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # 2.尾部增加数据
    def insert_at_tail(self, data):
        new_node = Node(data)
        # 是否是空链表查看
        if self.head is None:
            self.head = new_node
            return
        tail = self.head
        while tail.next is not None:
            tail = tail.next
        tail.next = new_node

    # 3.打印链表
    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=", ")
            current = current.next
        print()

    # 4.删除链表
    def remove_node(self, key):
        current = self.head
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next
        if current is None:
            print(f"没有找到{key}")
            return
        if prev is None:
            self.head = current.next
        else:
            prev.next = current.next

    # 5.查询链表
    def find_node(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    # 6.索引插入数据
    def insert(self, index, key):
        if index < 0:
            print("无用的index")
            return
        new_node = Node(key)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
        current = self.head
        for i in range(index - 1):
            if current is None:
                print("Index out of bounds.")
                return
            current = current.next
        if current is None:
            print("Index out of bounds.")
            return
        new_node.next = current.next
        current.next = new_node


if __name__ == '__main__':
    linked_list = ListNode()
    linked_list.insert_at_head(1)
    linked_list.insert_at_head(2)
    linked_list.insert_at_head(3)
    linked_list.insert_at_head(4)
    linked_list.print_list()
    linked_list.remove_node(1)
    linked_list.print_list()
    print(linked_list.find_node(3))
    linked_list.insert(2,45)
    linked_list.print_list()
